public class Sort {
    //直接插入排序
    //从小到大排序

    /**
     * 稳定的排序
     * @param array
     */
    public static void insertsort(int[] array) {
        //以一个标记指向已排序队列最后一个元素
          //j
        //以一个标记指向未排序队列
         //i
        for (int i = 1; i < array.length; i++) {
            int tmp = array[i];
             int j = i-1;
            for (; j >=0 ; j--) {
                if(tmp>array[j]){
                    array[j+1] = array[j];
                }else {    //插入排序是稳定排序还是非稳定排序？
                     array[j+1] = tmp;
                     break;
                }
            }
            //当所有值均比i下标的值大时
            array[j+1] = tmp;
        }
    }

    /**
     * 选择排序
     * 时间复杂度为O(N^2)
     * 空间复杂度为O(1)
     *
     */
    public static void selectSort(int []array){
        //对于一组数据进行选择排序
        for (int i = 0; i < array.length; i++) {
              int cur = i;
            for (int j = i+1; j < array.length; j++) {
                    if(array[j]<array[cur]){
                        cur = j;
                    }
            }
           //当遍历完数组之后，
            //将找到的最小值与当前i中的值交换
            int tmp = array[i];
            array[i] = array[cur];
            array[cur] = tmp;
        }
    }
/**
 * 直接选择排序
 * 既然可以从一次遍历中找到最小值，也就可以从一次遍历中找到最大值
 * 这样可以从两边逐渐确定
 *
 */
public static void  selectSort2(int []array){
        int left = 0;
        int right = array.length-1;
        while (left<right){
            int minindex = left;
            int maxindex = left;
            //在循环中变量值需要变化的值，不能够赋值常值
            for (int i = left+1; i <= right; i++) {
                  if(array[i]<array[minindex]){
                      minindex = i;
                  }
                  if(array[i]>array[maxindex]){
                       maxindex = i ;
                  }
            }
            //需要将最小的值，交换给left，将最大的值交换给right

            swap(array,minindex,left);
            //如果最大值为left，交换后，再执行下面的语句，便会出错
            if(left == maxindex){
                  maxindex = minindex;  //
            }
            swap(array,maxindex,right);
            left++;
            right--;
    }
}
private  static   void swap(int []array,int x,int y){
     //交换两个下标的值
     int tmp = array[x];
     array[x] =array[y];
     array[y] =tmp;
}









}